Constructive solid geometry (CSG) representations combine primitive shapes through regularized Boolean expressions. The primitive shapes define regularized solids, which may be represented as parameterized primitives, such as cylinders, blocks, or more general boundary representations. The Boolean expressions combine the primitives though regularized operations, such as union, intersection, or difference.
The set-theoretic Boolean expression of a CSG model may be parsed into a binary tree T, where each leaf corresponds to a primitive (or literal). The tree T in fact represents a Boolean expression, obtained by replacing the set-theoretic operators by their Boolean equivalent and by associating a truth-value with each leaf. The CSG expression is converted into a positive form Boolean expression E of n literals.
Boolean expressions are written in terms of literals and operations. Each occurrence of a variable is a different literal. For clarity, a different symbol (a, b, c . . . A, B, C . . . ) is used for each literal. Arbitrary Boolean expressions may be converted to their positive-form as follows. First, express all operators in terms of union, which is denoted by ‘+’, intersection, which is omitted or denoted by ‘·’ and complement, which is denoted by a preceding ‘!’ and endowed with highest priority. For example, the difference a\b is converted to a·(!b), or alternatively denoted as a!b, and the symmetric difference (logical XOR) ab is converted to a!b+b!a. Then, convert the expression into its positive form by recursively applying de Morgan laws: !!a=a, !(a+b)=!a!b, and !(ab)=!a+!b. Finally, replace all complemented literals with new literals that denote their complement. The result is an expression with n literals and n−1 operators, which are either ‘·’ or ‘+’. For example, the Boolean expression (a·b)+(c·(d+e)) has five literals and four operators. For simplicity, omitting ‘·’ and assuming that it has higher priority than ‘+’, the expression may be rewritten as ab+c(d+e). Remember that each occurrence of a variable is a different literal. Thus, for example, the expression a!b+b!a has four literals.
Parsing a positive-form expression E produces a binary tree T, whose 2n−1 nodes correspond each to a different literal or operator in E. For example, FIG. 1 is an illustration of a binary tree 100 representing the expression e+fg. The node 110, which corresponds to the final executed operator when evaluating E, is the “root”. Nodes 120 corresponding to literals are called “leaves”. Note that even though the same primitive may appear in several places in the CSG model, each instance has typically a different position and orientation and may yield a different classification of a surfel candidate. Hence, each primitive instance is treated as a different literal.
A non-leaf node is called an “op-node” (e.g. nodes 110 and 130). In a binary tree T, there are exactly n−1 op-nodes. In the binary tree 100 illustrated in FIG. 1, there are three leaves 120 and two op-nodes 110 and 130. If an op-node N corresponds to a Boolean combination (e.g. L+R or L·R) of two sub-expressions or literals, then L and R are respectively the “left and right children” of N and that N is their “parent”. In FIG. 1, leaves 120f and 120g are the left and right children, respectively, of op-node 130 and leaf 120e and the sub-expression fg (represented by nodes 120f, 120g, and 130) are the left and right children, respectively, of op-node 110. Each parent is separated from each one of its children by one “link” 140. The “distance” between two nodes is the number of links in the shortest path joining them. The “depth” of a node is the maximum distance separating it from its leaves. Hence, in FIG. 1, the depth of a leaf 120 is zero and the depth of the root 110 is two. A tree is “alternating” when no op-node has a parent with the same operator and a tree is “full” when the left and right children of each op-node have the same depth.